/*
 * @lc app=leetcode id=127 lang=cpp
 *
 * [127] Word Ladder
 */
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        vector<string> memo;
        int min = INT_MAX;
        memo.push_back(beginWord);
        ladderLength(beginWord, endWord, 0, min, memo, wordList);
        return min == INT_MAX ? 0 : min;
    }

    void ladderLength(string beg, string& end, int cnt, int& min,
            vector<string>& memo, vector<string>& wordList) {
        if (beg.compare(end) == 0) {
            if (min > memo.size()) {
                min = memo.size();
            }
            return;
        }

        for (auto& w : wordList) {
            if (beg.compare(w) != 0 && std::count(memo.begin(), memo.end(), w) == 0 && canTrans(beg, w)) {
                memo.push_back(w);
                ladderLength(w, end, cnt+1, min, memo, wordList);
                memo.pop_back();
            }
        }
    }

    bool canTrans(string& from, string& to) {
        int len = from.size();
        int cnt = 0;
        for (int i=0; i<len; i++) {
            if (from[i] != to[i]) {
                if (++cnt > 1) {
                    break;
                }
            }
        }
        return cnt == 1;
    }
};

